package com.zang.greedy;

import java.util.Arrays;

/**
 * @author ZVerify
 * @since 2022/11/23 09:42
 * @see <a href="https://leetcode.cn/problems/non-overlapping-intervals/">...</a>
 **/
public class 无重叠区间 {
    /**
     * 其实这个题和用最少数量的箭引爆气球差不多，因为这个也是区间
     * 我们可以拿一个箭就当做一个不重复的区间，如果重复的话那就是我们少算了x个，
     * 到最后一减去就是这个每个重复区间少算的x个就是我们需要删除的区间留下的都是不重叠的
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {

        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int sum = 1;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[i-1][1]) {
                sum++;
            }else {
                intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return intervals.length-sum;
    }
}
